#include<stdio.h>
#include<stdlib.h>
#include<string.h>
// #include"LinkTree.h"
#define true 1
#define false 0
#define ElementType int

struct BinaryTreeNode
{
    ElementType data;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
    struct BinaryTreeNode *parent;
};
typedef struct BinaryTreeNode BTNode;

struct BinaryLinkTree
{
    BTNode *root;
};
typedef struct BinaryLinkTree LBTree;

BTNode *CreateTreeNode(ElementType element)
{
    BTNode *treeNode=(BTNode *)malloc(sizeof(BTNode));
    if(treeNode==NULL)
    {
        printf("newNode malloc error!\n");
        return NULL;
    }
    treeNode->data=element;
    treeNode->left=NULL;
    treeNode->right=NULL;
    treeNode->parent=NULL;
    return treeNode;
}

int InitLBTree(LBTree *tree,ElementType element)
{
    tree->root=CreateTreeNode(element);
    if(tree->root==NULL)
    {
        printf("treeNode malloc error!\n");
        return false;
    }
    else
    {
        return true;
    }
    return 0;
}

void Insert(BTNode *node,ElementType element)
{
    if(node==NULL)
        return;
    if(node->left==NULL && element<node->data)
    {
        node->left=CreateTreeNode(element);
        node->left->parent=node;
        return;
    }
    if(node->right==NULL && element>node->data)
    {
        node->right=CreateTreeNode(element);
        node->right->parent=node;
        return;
    }
    if(element<node->data)
    {
        Insert(node->left,element);
    }
    else
    {
        Insert(node->right,element);
    }
}

void InsertLBTree(LBTree *tree,ElementType element)
{
    Insert(tree->root,element);
}

void MidPrint(BTNode *node)
{
    if(node!=NULL)
    {
        MidPrint(node->left);
        printf("%d ",node->data);
        MidPrint(node->right);
    }
}

void MidTravel(LBTree *tree)
{
    MidPrint(tree->root);
    printf("\n");
}

void PrevPrint(BTNode *node)
{
    if(node!=NULL)
    {
        printf("%d ",node->data);
        PrevPrint(node->left);
        PrevPrint(node->right);
    }
}

void PrevTravel(LBTree *tree)
{
    PrevPrint(tree->root);
    printf("\n");
}

void NextPrint(BTNode *node)
{
    if(node!=NULL)
    {
        NextPrint(node->left);
        NextPrint(node->right);
        printf("%d ",node->data);
    }
}

void NextTravel(LBTree *tree)
{
    NextPrint(tree->root);
    printf("\n");
}

void FreeNode(BTNode *node)
{
    if(node==NULL)
        return;
    FreeNode(node->left);
    FreeNode(node->right);
    FreeNode(node);
}

void FreeTree(LBTree *tree)
{
    FreeNode(tree->root);
    tree->root=NULL;
}

BTNode *SearchNode(BTNode *node,ElementType element)
{
    if(node==NULL)
        return NULL;
    if(node->data==element)
        return node;
    else if(node->data<element)
    {
        return SearchNode(node->right,element);
    }
    else
    {
        return SearchNode(node->left,element);
    }
}

BTNode *SearchElement(LBTree *tree,ElementType element)
{
    return SearchNode(tree->root,element);
}

void DeleteElement(LBTree *tree,ElementType element)
{
    BTNode *targetNode=SearchNode(tree->root,element);
    if(targetNode==NULL)
        return;
    if(targetNode->left==NULL && targetNode->right==NULL)
    {
        if(targetNode->parent->left==element)
        {
            targetNode->parent->left=NULL;
        }
        else
        {
            targetNode->parent->right=NULL;
        }
        free(targetNode);
    }
    else if(targetNode->right==NULL)
    {
        if(targetNode->parent==NULL)
        {
            tree->root=targetNode->left;
        }
        else if(targetNode->parent->left==targetNode)
        {
            targetNode->left->parent=targetNode->parent;
            targetNode->parent->left=targetNode->left;
        }
        else
        {
            targetNode->left->parent=targetNode->parent;
            targetNode->parent->right=targetNode->left;
        }
        free(targetNode);
    }
    else if(targetNode->left==NULL)
    {   
        if(targetNode->parent==NULL)
        {
            tree->root=targetNode->right;
        }
        else if(targetNode->parent->right==targetNode)
        {
            targetNode->right->parent=targetNode->parent;
            targetNode->parent->right=targetNode->right;
        }
        else
        {
            targetNode->right->parent=targetNode->parent;
            targetNode->parent->left=targetNode->right;
        }
        free(targetNode);
    }
}

int main()
{
    LBTree tree;
    int a[]={2,6,8,4,19,42,24,43};
    InitLBTree(&tree,a[0]);
    for(int i=1;i<sizeof(a)/sizeof(a[0]);i++)
    {
        InsertLBTree(&tree,a[i]);
    }
    MidTravel(&tree);
    PrevTravel(&tree);
    // NextTravel(&tree);

    BTNode *node=SearchElement(&tree,19);
    if(node!=NULL)
    {
        node->data=20;
    }
    MidTravel(&tree);
    return 0;
}